package 快速排序;

import java.util.Arrays;

public class 快速排序 {
	public static void main(String[] args) {
//		int[] arr = {5,6,7,8,4,3,2};
//		
////		quickSort(arr, 0, arr.length-1);
//		quickSort2(arr, 0, arr.length-1);
//		
//		System.out.println(Arrays.toString(arr));
		
		int[] longInt = new int[80000];
		for (int i = 0; i < longInt.length; i++) {
			longInt[i] = (int) (Math.random()*10000);
		}
		
		long star = System.currentTimeMillis();
		quickSort(longInt,0,longInt.length-1);
		long end = System.currentTimeMillis();
		System.out.println((end-star) + "毫秒");		//20-60ms  30ms
		System.out.println((end-star)/1000 + "秒");//0s
		
		System.out.println(Arrays.toString(longInt));
	}
	
	/**
	 * 快速排序 中间基准，两边同时进行，速度快步骤少，不需要 移动基准
	 * @param arr
	 * @param head
	 * @param tail
	 */
	public static void quickSort(int[] arr,int head,int tail) {
		if(head >= tail || arr.length <= 1 || arr == null) {
			return ;
		}
		int left = head;
		int right = tail;
		int piovt = arr[(left+right)/2];
		int temp = 0;
		
		
		while(left <= right) {
			//左指针到达基准之后就不动了
			while(arr[left] < piovt ) {
				left++;
			}
			while(arr[right] > piovt ) {
				right--;
			}
			if(left < right) {
				temp = arr[left];
				arr[left] = arr[right];
				arr[right] = temp;
				left++;
				right--;
//				System.out.println(Arrays.toString(arr));
			}else if(left == right){
				left++;
				//right--;  //参考代码这样写的，没有right--
				right--;
			}
		}
		
		quickSort(arr, head, right);
		quickSort(arr, left, tail);
	}
	
	/**
	 * 快速排序 最左边基准 ，左边基准，从右边开始，直到相遇，将基准和它交换，左右就分开了
	 * 在比较时，把基准也算进去，使用 <= 
	 * 
	 * 6,5,7,4,2,3,1	6为基准
	 * -6- , 5 , *7* , 4 , 2 , -3- , *1*	7和1交换，在3的位置相遇，交换6和3
	 * 3,5,1,4,2,6,7	从6左右分开成两个子序列
	 * 3,5,1,4,2		3为基准
	 * 
	 * @param arr
	 * @param head
	 * @param tail
	 */
	public static void quickSort2(int[] arr,int head,int tail) {
		if(head > tail || arr.length <= 1 || arr == null) {
			return ;
		}
		int left = head;
		int right = tail;
		int piovt = arr[left];
		int temp = 0;
		
		while(left < right) {
			// >= 范围可以把基准放过去
			//自增不是在交换之后，因为交换之后在此进入大循环，还要在比一次，然后自增，
			//右指针自减之后，左循环可能就不满足了，它们相遇
			while(arr[right] >= piovt && left < right) {
				right--;
			}
			while(arr[left] <= piovt && left < right) {
				left++;
			}
			
			//交换之后还要判断一次才自增
			if(left < right) {
				temp = arr[left];
				arr[left] = arr[right];
				arr[right] = temp;
			}
		}
		//把基准放到重合位置上
		arr[head] = arr[left];
		arr[left] = piovt;
		
		quickSort2(arr, head, left-1);
		quickSort2(arr, left+1, tail);
		
	}
}
